﻿/*****************************************介绍*****************************************
 * 作者：User
 * 创建时间：2025-09-09 18:54:03
 * 功能：路径查找
**************************************************************************************/

using System.Collections.Generic;
using static GameDataModel;

public class PathFinder
{
    /// <summary>
    /// 查找两个Item之间的最短可行路径
    /// </summary>
    /// <param name="item1">第一个选中的Item</param>
    /// <param name="item2">第二个选中的Item</param>
    /// <returns>包含路径上所有Item ID的列表，如果不可消除则返回null</returns>
    public List<int> FindPath(Item item1, Item item2, Level levle)
    {
        // 基础条件检查
        if (item1 == null || item2 == null ||
            item1.status != EItemStatus.Unlocked ||
            item2.status != EItemStatus.Unlocked ||
            item1.iconId != item2.iconId)
        {
            return null;
        }

        // 如果两个Item相邻，直接返回路径
        if (IsAdjacent(item1, item2))
        {
            return new List<int> { item1.id, item2.id };
        }

        // 使用BFS查找路径
        return BFSSearch(item1, item2, levle);
    }

    /// <summary>
    /// 检查两个Item是否相邻
    /// </summary>
    private bool IsAdjacent(Item a, Item b)
    {
        return (a.top != -1 && a.top == b.id) ||
               (a.bottom != -1 && a.bottom == b.id) ||
               (a.left != -1 && a.left == b.id) ||
               (a.right != -1 && a.right == b.id);
    }

    /// <summary>
    /// 使用广度优先搜索查找最短路径
    /// </summary>
    private List<int> BFSSearch(Item start, Item end, Level levle)
    {
        // 队列存储搜索节点（当前Item，路径，拐弯次数，移动方向）
        Queue<SearchNode> queue = new Queue<SearchNode>();

        // 初始化队列
        queue.Enqueue(new SearchNode(start, new List<int> { start.id }, 0, -1));

        while (queue.Count > 0)
        {
            var currentNode = queue.Dequeue();

            // 检查四个方向
            foreach (var direction in new[] { 0, 1, 2, 3 }) // 0:上, 1:下, 2:左, 3:右
            {
                int neighborId = GetNeighbor(currentNode.Item, direction);
                if (neighborId == -1) continue;
                Item neighbor = levle.items[neighborId];

                // 计算新的拐弯次数
                int newTurns = currentNode.Turns;
                if (currentNode.Direction != -1 && currentNode.Direction != direction)
                {
                    newTurns++;
                    if (newTurns > 2) continue; // 超过2个拐弯，跳过
                }

                // 如果找到终点
                if (neighbor.id == end.id)
                {
                    var path = new List<int>(currentNode.Path) { end.id };
                    return path;
                }

                // 检查邻居是否可通行（必须是已消除的状态）
                if (neighbor.status != EItemStatus.Destroyed) continue;

                // 检查是否已在当前路径中（避免循环）
                if (currentNode.Path.Contains(neighbor.id)) continue;

                // 创建新路径并加入队列
                var newPath = new List<int>(currentNode.Path) { neighbor.id };
                queue.Enqueue(new SearchNode(neighbor, newPath, newTurns, direction));
            }
        }

        return null; // 未找到路径
    }

    /// <summary>
    /// 获取指定方向的邻居的ID
    /// </summary>
    private int GetNeighbor(Item item, int direction)
    {
        switch (direction)
        {
            case 0: return item.top;     // 上
            case 1: return item.bottom;  // 下
            case 2: return item.left;    // 左
            case 3: return item.right;   // 右
            default: return -1;
        }
    }

    /// <summary>
    /// BFS搜索节点类
    /// </summary>
    private class SearchNode
    {
        public Item Item { get; }
        public List<int> Path { get; }
        public int Turns { get; }
        public int Direction { get; } // 0:上, 1:下, 2:左, 3:右, -1:起始点

        public SearchNode(Item item, List<int> path, int turns, int direction)
        {
            Item = item;
            Path = path;
            Turns = turns;
            Direction = direction;
        }
    }
}